package com.zwj.interview.BFS;


/**
 * 给定一棵二叉搜索树和它的一个节点p，请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的
 *
 * 中序遍历就是：左子树-->p-->右子树
 */
public class 寻找下一个节点 {


    /**
     *
     * 二叉搜索树：
     * 根节点的值大于其左子树的所有节点值
     * 根节点的值小于其右子树的所有节点值
     *
     * 对于任何节点来说，中序遍历的话，就是先遍历其左子树然后这个节点，最后其右子树
     *
     * 关键逻辑:
     * 这是关键：题目要求p的下一个节点，也就是要找到所有大于P节点的值的节点中最小的那个
     *
     */
    public TreeNode inOrderSuccessor(TreeNode root, TreeNode p) {
       TreeNode cur=root;
       TreeNode result=null;
        /**
         * 用变量result记录节点p的下一个节点。每当找到一个值大于p的节点，就更新变量result，
         * 并接着前往左子树看能否找到值更小但仍然大于节点p的值的节点。那么最后result就是所有大于节点p的值的节点中值最小的节点，
         * 也就是节点p的下一个节点
         */
       while(cur!=null){
           //从root开始,如果当前的节点大于p的值，就暂存，然后往左边走，缩小cur的值
           if(cur.val>p.val){
               result=cur;
               cur=cur.left;
           }else{
               //当前节点小于p,往右走
               cur=cur.right;
           }
       }
       //中序遍历的话p的下一个节点就是值大于等于p的节点中，值最小的一个，抓住这一点
       return result;
    }





}
